#include <iostream>
#include <vector>
#include <stack>

using namespace std;
// 150. 逆波兰表达式求值
// 给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。
// 请你计算该表达式。返回一个表示表达式值的整数。
// 注意：
//有效的算符为 '+'、'-'、'*' 和 '/' 。每个操作数（运算对象）都可以是一个整数或者另一个表达式。
// 两个整数之间的除法总是 向零截断 。表达式中不含除零运算。
//输入是一个根据逆波兰表示法表示的算术表达式。
//答案及所有中间计算结果可以用 32 位 整数表示。
//示例 1：
//输入：tokens = ["2","1","+","3","*"]
//输出：9
//解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        for(auto op : tokens) { // 遍历字符串数组
            if(op.length() > 1 || isdigit(op[0]))   // 数字
                st.push(stoi(op));  // 字符串转为整数入栈
            else {  // 运算符
                int b = st.top(); st.pop();
                int a = st.top(); st.pop();
                switch (op[0]) {
                    case '+':
                        st.push(a+b);
                        break;
                    case '-':
                        st.push(a-b);
                        break;
                    case '*':
                        st.push(a*b);
                        break;
                    case '/':
                        st.push(a/b);
                        break;
                }
            }
        }
        return st.top();
    }

private:
    stack<int> st;
};

int main() {
    std::cout << "Hello, World!" << std::endl;
    return 0;
}
